/*
https://leetcode-cn.com/problems/decode-ways-ii/solution/jie-ma-fang-fa-ii-by-leetcode-solution-23af/
 */
public class Solution639 {
    private static final int MOD = 1000000007;
    public int numDecodings(String s) {
        long a=0,b=1,c=0;
        for (int i=0;i<s.length();i++){
            int l=left(s.charAt(i));
            int r=0;
            if (i>0){ r=right(s.charAt(i-1),s.charAt(i));}
            c=((l*b)%MOD+(r*a)%MOD)%MOD;
            a=b;b=c;
        }
        return (int) b;
    }

    private int left(char c){
        switch (c){
            case '*':return 9;
            case '0':return 0;
            default:return 1;
        }
    }

    private int right(char c1,char c2){
        if (c1=='*'){
            if (c2=='*') return 15;
            if (c2>='0'&&c2<='6') return 2;
            return 1;
        }else{
            if (c2=='*'){
                if (c1=='1') return 9;
                if (c1=='2') return 6;
                return 0;
            }else{
                int t=(c1-'0')*10+c2-'0';
                if (t>=10&&t<=26){
                    return 1;
                }else{
                    return 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution639().numDecodings("2*"));
    }
}
